2022-12-20-OSU拓展

B 君并不喜欢 OSU，但是 B 君觉得 OSU 这个题不错。

输入 和 ，一共有 次点击，每次可以可能成功或失败。

对于一段长度为 连续极长的成功点击序列，得分是 。

已知第 次点击的成功率是 。

问期望得分是多少？

因为得分可能很大，并且不是整数，只需要输出得分模 1000000007 的结果即可。

对算法正确性的说明：2023-01-17-再看OSU拓展

#include <bits/stdc++.h>
using namespace std;
int n, m, mod = 1000000007;
long long p[100020];
long long a[1020];
long long b[1020];
long long s[1020][120];
long long f[1020];
int main() {
	scanf("%d%d", &n, &m);
	s[0][0] = 1;
	for (int i = 0; i <= m; i++) {
		for (int j = 1; j <= i; j++) {
			s[i][j] = (s[i - 1][j - 1] + j * s[i - 1][j]) % mod;
		}
	}
	for (int i = f[0] = 1; i <= m; i++) {
		f[i] = f[i - 1] * i % mod;
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &p[i]);
		p[i] = p[i] * 570000004 % mod;
		for (int j = m; j > 0; j--) {
			a[j] += a[j - 1];
			a[j] *= p[i];
			a[j] %= mod;
			b[j] += a[j];
			b[j] %= mod;
		}
		a[0] = p[i];
		b[0] += a[0];
		b[0] %= mod;
	}
	long long z = 0;
	for (int i = 1; i <= m; i++) {
		z = (z + b[i - 1] * f[i] % mod * s[m][i]) % mod;
	}
	printf("%lld\n", z);
	return 0;
}
Copy